1. Field of the Invention
The present invention generally relates to transform coding of digital data, specifically to processing of transformed data and, more particularly, to a shift and/or merge of two-dimensional transformed data using hybrid domain processing which increases the speed of, for example, processing of color images printed by color printers. The invention implements an efficient method for two-dimensional merging and shifting of JPEG (Joint Photographic Experts Group) images compressed with the Discrete Cosine Transform (DCT) domain. Since each dimension is handled separately, the shift or merge amounts are independent for the two axes. The invention provides fast shifting of the basic 8xc3x978 DCT blocks contained in baseline JPEG compressed images to create JPEG images on a new grid.
Transform coding is the name given to a wide family of techniques for data coding, in which each block of data to be coded is transformed by some mathematical function prior to further processing. A block of data may be a part of a data object being coded, or may be the entire object. The data generally represent some phenomenon, which may be for example a spectral or spectrum analysis, an image, a video clip, etc. The transform function is usually chosen to reflect some quality of the phenomenon being coded; for example, in coding of still images and motion pictures, the Fourier transform or Discrete Cosine Transform (DCT) can be used to analyze the data into frequency terms or coefficients. Given the phenomenon being compressed, there is generally a concentration of the information into a few frequency coefficients. Therefore, the transformed data can often be more economically encoded or compressed than the original data. This means that transform coding can be used to compress certain types of data to minimize storage space or transmission time over a communication link.
An example of transform coding in use is found in the Joint Photographic Experts Group (JPEG) international standard for still image compression, as defined by ITU-T Rec. T.81 (1992) ISO/IEC 10918-1:1994, Information technologyxe2x80x94Digital compression and coding of continuous-tone still images, Part 1: Requirements and Guidelines. Another example is the Moving Pictures Experts Group (MPEG) international standard for motion picture compression, defined by ISO/IEC 11172:1993, Information Technologyxe2x80x94Coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbits/s. This MPEG-1 standard defines a video compression (Part 2 of the standard). A more recent MPEG video standard (MPEG-2) is defined by ITU-T Rec. H.262 ISO/IEC 13818-2: 1996 Information Technologyxe2x80x94Generic Coding of moving pictures and associated audioxe2x80x94Part 2: video. All three image international data compression standards use the DCT on 8xc3x978 blocks of samples to achieve image compression. DCT compression of images is used herein to give illustrations of the general concepts put forward below; a complete explanation can be found in Chapter 4 xe2x80x9cThe Discrete Cosine Transform (DCT)xe2x80x9d in W. B. Pennebaker and J. L. Mitchell, JPEG: Still Image Data Compression Standard, Van Nostrand Reinhold: New York, (1993).
Wavelet coding is another form of transform coding. Special localized basis functions allow wavelet coding to preserve edges and small details. For compression the transformed data is usually quantized. Wavelet coding is used for fingerprint identification by the Federal Bureau of Investigation (FBI). Wavelet coding is a subset of the more general subband coding technique. Subband coding uses filter banks to decompose the data into particular bands. Compression is achieved by quantizing the lower frequency bands more finely than the higher frequency bands while sampling the lower frequency bands more coarsely than the higher frequency bands. A summary of wavelet, DCT, and other transform coding is given in Chapter 5 xe2x80x9cCompression Algorithms for Diffuse Dataxe2x80x9d in Roy Hoffman, Data Compression in Digital Systems, Chapman and Hall: New York, (1997).
In any technology and for any phenomenon represented by digital data, the data before a transformation is performed are referred to as being xe2x80x9cin the real domainxe2x80x9d. After a transformation is performed, the new data are often called xe2x80x9ctransform dataxe2x80x9d or xe2x80x9ctransform coefficientsxe2x80x9d, and referred to as being xe2x80x9cin the transform domainxe2x80x9d. Since the present invention works on multi-dimensional transformed data after taking the inverse transform on less than the total dimension, we are defining a new term, xe2x80x9chybrid domainxe2x80x9d, to indicate that the orthogonal axis/axes is still transformed. To simplify notation, we will describe the invention for two dimensional transform data. Unless the context makes another meaning clear, the term xe2x80x9ctransform domainxe2x80x9d will refer to the full multi-dimensional transform domain. The function used to take data from the real domain to the transform domain is called the xe2x80x9cforward transformxe2x80x9d. The mathematical inverse of the forward transform, which takes data from the transform domain to the real domain, is called the respective xe2x80x9cinverse transformxe2x80x9d.
In general, the forward transform will produce real-valued data, not necessarily integers. To achieve data compression, the transform coefficients are converted to integers by the process of quantization. Suppose that (xcexi) is a set of real-valued transform coefficients resulting from the forward transform of one unit of data. Note that one unit of data may be a one-dimensional or two-dimensional block of data samples or even the entire data. The xe2x80x9cquantization valuesxe2x80x9d (qi) are parameters to the encoding process. The xe2x80x9cquantized transform coefficientsxe2x80x9d or xe2x80x9ctransform-coded dataxe2x80x9d are the sequence of values (ai) defined by the quantization function Q:                                           a            i                    =                                    Q              ⁡                              (                                  λ                  i                                )                                      =                          ⌊                                                                    λ                    i                                                        q                    i                                                  +                0.5                            ⌋                                      ,                            (        1        )            
where └x┘ means the greatest integer less than or equal to x.
The resulting integers are then passed on for possible further encoding or compression before being stored or transmitted. To decode the data, the quantized coefficients are multiplied by the quantization values to give new xe2x80x9cdequantized coefficientsxe2x80x9d (xcexixe2x80x2) given by
xcexixe2x80x2=qiarxe2x80x83xe2x80x83(2)
The process of quantization followed by de-quantization (also called inverse quantization) can thus be described as xe2x80x9crounding to the nearest multiple of qixe2x80x9d. The quantization values are chosen so that the loss of information in the quantization step is within some specified bound. For example, for image data, one quantization level is usually the smallest change in data that can be perceived. It is quantization that allows transform coding to achieve good data compression ratios. A good choice of transform allows quantization values to be chosen which will significantly cut down the amount of data to be encoded. For example, the DCT is chosen for image compression because the frequency components which result produce almost independent responses from the human visual system. This means that the coefficients relating to those components to which the visual system is less sensitive, namely the high-frequency components, may be quantized using large quantization values without loss of image quality. Coefficients relating to components to which the visual system is more sensitive, namely the low-frequency components, are quantized using smaller quantization values.
The inverse transform also generally produces non-integer data. Usually the decoded data are required to be in integer form. For example, systems for the display of image data generally accept input in the form of integers. For this reason, a transform decoder generally includes a step that converts the non-integer data from the inverse transform to integer data, either by truncation or by rounding to the nearest integer. There is also often a limit on the range of the integer data output from the decoding process in order that the data may be stored in a given number of bits. For this reason the decoder also often includes a xe2x80x9cclippingxe2x80x9d stage that ensures that the output data are in an acceptable range. If the acceptable range is [a, b], then all values less than a are changed to a, and all values greater than b are changed to b.
These rounding and clipping processes are often considered an integral part of the decoder, and it is these which are the cause of inaccuracies in decoded data and in particular when decoded data are re-encoded. For example, the JPEG standard (Part 1) specifies that a source image sample is defined as an integer with precision P bits, with any value in the range 0 to 2Pxe2x88x921. The decoder is expected to reconstruct the output from the inverse discrete cosine transform (IDCT) to the specified precision. For the baseline JPEG coding P is defined to be 8; for other JPEG DCT-based coding P can be 8 or 12. The MPEG-2 video standard states in Annex A (Discrete Cosine Transform), xe2x80x9cThe input to the forward transform and the output from the inverse transform is represented with 9 bits.xe2x80x9d
For the JPEG standard, the compliance test data for the encoder source image test data and the decoder reference test data are 8 bit/sample integers. Even though rounding to integers is typical, some programming languages convert from floating point to integers by truncation. Implementations in software that accept this conversion to integers by truncation introduce larger errors into the real-domain integer output from the inverse transform.
The term xe2x80x9chigh-precisionxe2x80x9d is used herein to refer to numerical values which are stored to a precision more accurate than the precision used when storing the values as integers. Examples of high-precision numbers are floating-point or fixed-point representations of numbers.
In performing a printing operation, there is a need for the printer to be able to merge a portion of an 8xc3x978 Discrete Cosine Transform (DCT) domain block with the complementary portion of a second DCT block quickly. The traditional approach involves conversion from the DCT domain for each of the original blocks to the respective real domains (each a 64-bit sample space) via an inverse DCT followed by merging the components of interest from each block in the real domain and finally transforming this new image back to the DCT domain. This method involves more computations than is necessary and lengthens total processing time.
While it is commonplace for graphics utilities to merge two independent images with brute force pixel-by-pixel merges as described above, it is also possible to approach the problem by working exclusively in the frequency domain. This approach potentially has at least two advantages over the traditional method in that it (1) provides for faster and more flexible image processing than the traditional technology and (2) eliminates errors which routinely take place when working in the real domain with fixed precision computation by avoiding the real domain entirely. The invention described in copending application Ser. No. 09/524,389 works exclusively in the transform domain.
The present invention relates to processing in an intermediate domain, called the xe2x80x9chybridxe2x80x9d domain, a domain between the transform domain and the real domain. This type of processing is called hybrid domain processing.
2. Background Description
The purpose of image compression is to represent images with less data in order to save storage costs or transmission time and costs. The most effective compression is achieved by approximating the original image, rather than reproducing it exactly. The JPEG standard allows the interchange of images between diverse applications and opens up the capability to provide digital continuous-tone color images in multi-media applications. JPEG is primarily concerned with images that have two spatial dimensions, contain grayscale or color information, and possess no temporal dependence, as distinguished from the MPEG (Moving Pictures Experts Group) standard. The amount of data in a digital image can be extremely large, sometimes being millions of bytes. JPEG compression can reduce the storage requirements by more than an order of magnitude and improve system response time in the process.
One of the basic building blocks for JPEG is the Discrete Cosine Transform (DCT). An important aspect of this transform is that it produces uncorrelated coefficients. Decorrelation of the coefficients is very important for compression because each coefficient can be treated independently without loss of compression efficiency. Another important aspect of the DCT is the ability to quantize the DCT coefficients using visually-weighted quantization values. Since the human visual system response is very dependent on spatial frequency, by decomposing an image into a set of waveforms, each with a particular spatial frequency, it is possible to separate the image structure the eye can see from the structure that is imperceptible. The DCT provides a good approximation to this decomposition.
The most straightforward way to implement the DCT is to follow the theoretical equations. When this is done, an upper limit of 64 multiplications and 56 additions is required for each one-dimensional (1-D) 8-point DCT. For a full 8xc3x978 DCT done in separable one-dimensional formatxe2x80x94eight rows and then eight columnsxe2x80x94would require 1,024 multiplications and 896 additions plus additional operations to quantize the coefficients. In order to improve processing speed, fast DCT algorithms have been developed. The origins of these algorithms go back to the algorithm for the Fast Fourier Transform (FFT) implementation of the Discrete Fourier Transform (DFT). The most efficient algorithm for the 8xc3x978 DCT requires only 54 multiplications, 464 additions and 6 arithmetic shifts.
The two basic components of an image compression system are the encoder and the decoder. The encoder compresses the xe2x80x9csourcexe2x80x9d image (the original digital image) and provides a compressed data (or coded data) output. The compressed data may be either stored or transmitted, but at some point are fed to the decoder. The decoder recreates or xe2x80x9creconstructsxe2x80x9d an image from the compressed data. In general, a data compression encoding system can be broken into three basic parts: an encoder model, an encoder statistical model, and an entropy encoder. The encoder model generates a sequence of xe2x80x9cdescriptorsxe2x80x9d that is an abstract representation of the image. The statistical model converts these descriptors into symbols and passes them on to the entropy encoder. The entropy encoder, in turn, compresses the symbols to form the compressed data. The encoder may require external tables; that is, tables specified externally when the encoder is invoked. Generally, there are two classes of tables; model tables that are needed in the procedures that generate the descriptors and entropy-coding tables that are needed by the JPEG entropy-coding procedures. JPEG uses two techniques for entropy encoding: Huffman coding and arithmetic coding. Similarly to the encoder, the decoder can be broken into basic parts that have an inverse function relative to the parts of the encoder.
JPEG compressed data contains two classes of segments: entropy-coded segments and marker segments. Other parameters that are needed by many applications are not part of the JPEG compressed data format. Such parameters may be needed as application-specific xe2x80x9cwrappersxe2x80x9d surrounding the JPEG data; e.g., image aspect ratio, pixel shape, orientation of image, etc. Within the JPEG compressed data, the entropy-coded segments contain the entropy-coded data, whereas the marker segments contain header information, tables, and other information required to interpret and decode the compressed image data. Marker segments always begin with a xe2x80x9cmarkerxe2x80x9d, a unique 2-byte code that identifies the function of the segment.
There is a need for fast shifting of the basic 8xc3x978 DCT blocks contained in baseline JPEG compressed images to create JPEG images on a new grid. There is also a need to merge two JPEG images into a combined JPEG compressed image. The amount of shift xe2x80x9cmxe2x80x9d (or the number of sample-rows or sample-columns xe2x80x9cmxe2x80x9d from the first image""s blocks to be merged into a new block) are independent of the horizontal and vertical axes.
Traditionally, graphics utilities operate by first doing the two-dimensional (2-D) inverse transform back to the real domain and then working pixel by pixel. The pixel values have been converted to finite precision (usually 8-bits/component sample). The new two-dimensional blocks are generated by doing the two-dimensional forward transform on the processed image. The two-dimensional inverse and forward transform contain too many operations to be fast enough for high speed printing operations. Fast paths exist for the inverse DCT (IDCT) which, due to quantization, has many coefficients of zero. These special cases are estimated to improve throughput by about a factor of three. However, the forward DCT (FDCT) does not have similar fast paths because no pixel values are likely to be zero.
According to the invention, the solution provided does a one- dimensional (1D) inverse DCT (IDCT) to the input two-dimensional (2D) transform blocks along the axis to be modified. Since the one-dimensional IDCT is not performed on the other axis, each block is neither real data nor transform data. It is called hybrid data. For a shift (merge), the appropriate xe2x80x9cmxe2x80x9d elements are picked up from one block and the xe2x80x9c8xe2x88x92mxe2x80x9d elements are picked up from the other block (in a different image for the merge) and are used as input to the one-dimensional forward DCT (FDCT) along that same axis. The re-quantization step can be merged into the final one-dimensional FDCTs. For two-dimensional shifts or merges, the results of the first one-dimensional IDCT and FDCT can be stored with extra precision to be used as input to a second one-dimensional IDCT and FDCT along the other axis. Note that the only difference between the shift and merge (assuming correct alignment of the participating blocks) is the location of the second block. In the shift case, it is the adjacent block in the image along the desired axis. In the merge case, it is from another image.
There are several advantages of handling operations on two-dimensional transform blocks such as the two-dimensional shift and/or merge by doing the one-dimensional IDCT, the operation along that axis, and the one-dimensional FDCT and then repeating for the other axis. These include the following:
1. The computations for the one-dimensional IDCT have known fast paths. For columns (or rows) along the direction of block change that contain only zero elements in both blocks (usually at least half the columns or rows), the one-dimensional IDCT calculation, shift/merge, and then the one-dimensional FDCT calculation can be skipped because the result has only zeros for elements. After a full two-dimensional IDCT, few elements are zero.
2. This invention takes advantage of the fast one-dimensional IDCT and FDCT code which may already be implemented and optimized for the product.
3. This invention eliminates the need for special, separate cases for the different xe2x80x9cmxe2x80x9d shift or merge amounts.
4. The generic shift of the two-dimensional DCT block by (m,n) should execute faster than any other known method. The merge operation should execute in similar times. The execution times for all combinations of m and n should be about the same.
5. For one-dimensional operations on the two-dimensional transform blocks, the process is much faster than having to perform the full two-dimensional inverse transform to get to the real domain and then the full two-dimensional forward transform to get back the transform two-dimensional blocks.
6. The precision after the one-dimensional IDCTs and the first one-dimensional FDCTs is maintained sufficiently to eliminate concerns about multi-generation problems. The second one-dimensional IDCT along the orthogonal axis does not need to include dequantization if the first FDCT does not include quantization. The quantization is done after the second IDCTs.
This invention will also work for other orthogonal transforms or even higher dimensionality orthogonal transformations if they are fully separable into one-dimensional transforms along each axis. It works for other processing besides the shift and merge examples as long as the original full inverse transform, processing in the real domain, full forward transform can be mathematically separated into one-dimensional inverse transformations, a less than full inverse transform can be performed, the processing done in the resulting hybrid transform space, and then the corresponding forward transform performed to return to the full multi-dimensional transform.